package hot;

import java.util.ArrayList;
import java.util.List;

public class sanjiu {
//    https://leetcode.cn/problems/combination-sum/?envType=study-plan-v2&envId=top-100-liked

        static List<List<Integer>> ret=new ArrayList<>();
        static List<Integer> path=new ArrayList<>();
        static int m=0;
        static int n;
        public static List<List<Integer>> combinationSum(int[] candidates, int target) {
            n=target;
            dfs(candidates,0);
            return ret;
        }
        public static void dfs(int[] candidates, int pos){
            if(m==n){
                ret.add(new ArrayList(path));
                return;
            }
            if(m<n){
                for(int i=pos;i<candidates.length;i++){
                    path.add(candidates[i]);
                    m+=candidates[i];
                    dfs(candidates,i);
                    //恢复现场
                    int h=path.get(path.size()-1);
                    m-=h;
                    path.remove(path.size()-1);
                }
            }
        }

    public static void main(String[] args) {
        int[] nums={2,3,5};
        List<List<Integer>> list = combinationSum(nums, 8);
        System.out.println(list);

    }
    }

